剑指Offer 23 从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路

层序遍历二叉树；每一层从右开始输出；按照一般的遍历方法，左节点，右节点，那么在遍历左节点时，就应该将左节点的子节点保存下来，然后是右节点的子节点；然后统一输出；FIFO，先到先出即为队列；

定义一个队列，将根节点放进去; 当队列不为空的时候， 获取队列的顶部元素，即当前的节点；有左子节点，就把左节点放进队列，有右子节点，放右节点；输出当前根节点的值；

代码

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
       ArrayList<Integer> arrayList= new ArrayList<>();
       if (root==null)
           return arrayList;
       TreeNode node = root;
       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(root);
       while (!queue.isEmpty())
       {
           TreeNode treeNode = queue.poll();
           if (treeNode.left!=null)
           {
               queue.offer(treeNode.left);
           }
           if (treeNode.right!=null)
           {
               queue.offer(treeNode.right);
           }
           arrayList.add(treeNode.val);
       }
       return arrayList;

   }

扩展

二叉树的先序，中序，后序遍历
例如：求下面树的三种遍历

前序遍历：abdefgc
中序遍历：debgfac
后序遍历：edgfbca

我们发现，其实代码是类似的，都是递归，只不过输出的不一样；

1. 先序是，递归到哪里，就输出当前节点；左节点输出完，输出右节点；从上到下；
2. 中序是：先输出最左面的；在递归中，它没有左子节点了，那就输出它；从左到右，如果一个节点的左子节点没有输出，就去输出左子节点，然后是右子节点；右子节点有左节点的话，继续左面输出优先
3. 后序是，如果一个节点下面的节点没有输出，就先输出下面；自下而上，自左到右的输出；

public static void preOrderTraverse(TreeNode node) {
    if (node == null)
        return;
    System.out.print(node.val + " ");
    preOrderTraverse(node.left);
    preOrderTraverse(node.right);
}

  
public static void inOrderTraverse(TreeNode node) {
    if (node == null)
        return;
    inOrderTraverse(node.left);
    System.out.print(node.val + " ");
    inOrderTraverse(node.right);
}

public static void postOrderTraverse(TreeNode node) {
    if (node == null)
        return;
    postOrderTraverse(node.left);
    postOrderTraverse(node.right);
    System.out.print(node.val+ " ");
}

收获

1. 第一次使用队列，Queue是一个接口，一般使用LinkedList初始化
2. offer是添加元素，poll是弹出元素